package com.algorithm.dichotomy;

/**
 * 二维数组的查找
 * 题目:在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
 * 请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 *思路：因为数组每一行是从左到右依次递增排序的，所以查找时应该使用二分法查找
 * 二分法查找原理：取中间数据与输入数据做对比，如果输入数据大与中间数据，那么输入数据的位置在后面一半，就将头结点定于中间索引加1，
 * 如果输入数据小于中间数据，那么输入数据的位置就在前面一半，就讲尾结点位置定于中间位置索引减1.
 */
public class ArraySearch {
    public static void main(String[] args) {
        int[][] array = {{1,2,4,6,7}, {2,4,6,7,9}, {1,4,5,6,7} };
        System.out.println(Find(3,array));
    }
    public static boolean Find(int target, int [][] array) {
        for (int i=0;i<array.length;i++){
            int low =0;
            int high=array[i].length-1;
            while(low <=high){
                int mid=(low+high)/2;
                if (target>array[i][mid]){
                    low=mid+1;
                }else if (target<array[i][mid]){
                    high=mid-1;
                }else{
                    return true;
                }
            }
        }
        return false;
    }
}
